package DP;

/**
 * 746.使用最小花费爬楼梯
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 * dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
 */
public class minCostClimbingStairs {
    /**
     * 一刷，一刷二刷思路一致
     */
    public int minCostClimbingStairs(int[] cost) {

        int n = cost.length;
        int sum[] = new int[n + 1];

        sum[0] = 0;
        sum[1] = 0;
        for (int i = 2; i <= n; i++) {
            sum[i] = Math.min(sum[i - 2] + cost[i - 2], sum[i - 1] + cost[i - 1]);
        }
        return sum[n];
    }

    /**
     * 二刷
     */
    public int minCostClimbingStairs2(int[] cost) {
        int[] dp = new int[cost.length + 1];
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}
